package top.k.frequent;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Time 2020/1/3
 * @author 王光浩
 * @Need 给出一个整型数组，找出其中前k个出现频率最高的数字。
 * @Thinking 打榜算法。使用一个HashMap，两个整型数组。
 *           
 *           思路：首先遍历数组nums，将所有元素值加入到第一个HashMap中，并统计出现次数，然后遍历第一个
 *           HashMap，将第一个HashMap中的mapping颠倒之后依次加入到第二个HashMap中，但是第二个HashMap的大小有一
 *           限制，最大不能超过k，如果超过k的话，就判断待加入的元素的value是否大于第二个HashMap中
 *           最小的key，如果大于则移除最小的key，然后将该元素加入第二个HashMap中，最后将第二个HashMap中的所有value
 *           作为结果集返回。（但是我们忽略了一点那就是不同的元素可能会有相同的出现次数，但是HashMap不能
 *           添加相同key值元素，所以在思考之后打算使用两个长度为k的数组，一个用于保存元素的的值，一个用于
 *           保存对应元素的出现次数）——本质上就是打榜，榜上名额只有k个，遍历第二个HashMap，如果当前待
 *           加入的元素的出现次数小于榜上最小出现次数的元素，并将其取代。
 *           
 *           复杂度分析：时间复杂度O（n+k+nk-k^2）,空间复杂度O（2k+n）,k为k值，n为数组的长度。
 *           
 */
public class MyMethodOne {
    public List<Integer> topKFrequent(int[] nums, int k) {
    	HashMap<Integer,Integer> caculate=new HashMap<Integer,Integer>();
    	List<Integer> element=new ArrayList<Integer>();  //便于将结果返回时使用
    	int[] count=new int[k];                          //存储前k个元素的出现次数
    	int len=nums.length;
    	int minIndex=-1;
    	int isFull=0;
    	//整合nums中的元素，并统计次数
    	for(int i=0;i<len;i++) {
    		caculate.put(nums[i],caculate.getOrDefault(nums[i], 0)+1);
    	}
    	//获取前k个元素
    	for(Map.Entry<Integer, Integer> entry : caculate.entrySet()) {
    		if(isFull!=k) {
    			element.add(entry.getKey());
    			count[isFull++]=entry.getValue();
    			continue;
    		}
    		minIndex=(minIndex==-1)?getIndex(count):minIndex;
    		if(count[minIndex]<entry.getValue()) {
    			element.set(minIndex, entry.getKey());
    			count[minIndex]=entry.getValue();
    			minIndex=getIndex(count);
    		}
    	}
    	return element;
    }
    
    /**获取出现次数最小元素所在下标*/
    private int getIndex(int[] count) {
    	int k=count.length;
    	int minIndex=0;
    	int minValue=count[0];
    	for(int i=0;i<k;i++) {
    	  if(count[i]<minValue) {
    		  minIndex=i;
    		  minValue=count[i];
    	  }
    	}
    	return minIndex;
    }
}
